The invention relates to asymmetric cryptographic communication processes, in particular the multivariate public key cryptosystems (MPKC), to provide secure communication and secure authentication or signature.
The revolutionary idea of a public key cryptosystem, which has since fundamentally changed our modern communication system, was first suggested by Diffie and Hellman, though the first practical realization of this idea was the famous RSA cryptosystem by Rivest, Shamir and Adleman. (U.S. Pat. No. 4,405,829, 1983)
Multivariate public key cryptosystems are public key cryptosystems whose building blocks are multivariable polynomials, mostly, quadratic polynomials. This method relies on the proven theorem that solving a set of multivariable polynomial equations over a finite field, in general, is an NP-hard problem. This provides the possibility that they could resist even the future quantum computer attack while RSA can not [Sp], and due to the fast computation on small finite fields, they are much more efficient than RSA in general.
Early attempts like of Diffie and Fell [DF], and Shamir [Sh] failed.
A new design of multivariate cryptosystems was started by Matsumoto and Imai [MI] in 1988, which looked very promising but was defeated by Patarin in 1995 [P]. However many new systems are built inspired by this work.
1) Minus-Plus generalization. [CGP1] This is the simplest idea among all, namely one takes out (Minus method, which was first suggested in [Sh]) a few of the quadratic polynomial components of the cipher, and (or) adds (Plus method) a few randomly chosen quadratic polynomials. The main reason to take the “Minus” action is to improve the security [SH]. The Minus (only) method is very suitable for signature schemes, because it does not require that a documents to have a unique signature unlike the case of decryption process. Sflash [ACDG,CGP] is a Matsumoto-Imai-Minus cryptosystem. It was selected in 2004 by the NESSIE, the New European Schemes for Signatures, Integrity, and Encryption project within the Information Society Technologies (IST) Programme of the European Commission as one of the security standards for low-cost smart card applications after more than three years of screening process.
2) Hidden Field Equation Method. (HFE) [P1]. This method is suggested by Patarin to be the strongest. However a new algebraic attack using both the Minrank method and the relinearization method by Kipnis and Shamir [KS] shows that a special parameter can not be too small, but if this parameter is big, the system is just too slow. HFE is patented in Europe and US (U.S. Pat. No. 5,790,675, 1998). This is further confirmed in [FJ].
A new system proposed recently by Wang, Yang, Hu and Lai also is related to this family. [WYHL].
3) Vinegar-Oil method. The (balanced) Oil and Vinegar schemes and the unbalance Oil and Vinegar schemes [P3] [KPG] are new constructions of signature schemes. The balanced case was defeated by Kipnis and Shamir[Sh1]. The unbalanced case in general is not very efficient because the signature is more than twice the length of the document (or the hash of a document).
4) HFEV. The basic idea of this system is, on top of the HFE method, to add a few new external variables to make the system more complicated. This is a combination of HFE and Oil-Vinegar. Ding and Schmidt [DS3] recently observed that the attack in [KS] can also be applied to actually eliminate the small number of added variables and attack the system. A signature scheme Quartz was proposed as a HFE-Minus scheme and it has a very short signature of 128 bits [CGP2], but it is rather slow.
Another family is the triangular construction by T. T. Moh [M1] using special triangular type of invertible maps (Tame transformations). This method is named the tame transformation method (TTM). (U.S. Pat. No. 5,740,250, 1998) Courtois and Goubin [CM] used a method of minrank to attack this system. However the inventor of TTM refuted the claim in [CM], where they gave a new implementation schemes to support their claim. Later, Ding and Schmidt [DS1] [DS2] found out that actually all existing implementation schemes at the time have a common defect that could make them insecure. A new scheme is also proposed recently [MCY].
Attempts were made to use a similar but simpler idea for signature, which was called a TTS (tamed transformation signature) scheme. A few of them were suggested mainly by Chen and his collaborators [YC] [CYP]. A new construction of TTS [YCC] was proposed, but was defeated by Ding and Yin [DY]. Another new version is proposed in [YC1]. A similar construction was also proposed in [WHLCY] (US patent application: 20040151307, 2004).
The original ideal of internal perturbation was fist proposed by Ding. (US Patent application: 20030215093, 2003). This idea was applied to the Matsumoto-Imai system mentioned above in [D]. However this case was defeated by Pierre-Alain Fouque and Louis Granboulan and Jacques Stern [GGS]. As a further improvement, we proposed the Internal-Perturbation-Plus in this application. It is applied to the Matsumoto-Imai cryptosystem, which, we show, can effective resist all attacks [DG]. Another improvement is the enhanced internal perturbation, which is applied to HFE. [DS3].
The general multi-layer construction of ours was first applied to Oil-Vinegar case, which builds the rainbow system [DS4]. Both [YC1] and [WHLCY] are special examples of our general construction.